/*
 * Lab10B.cpp
 *
 *  Created on: 2014-04-20
 *      Author: Anthony Varghese
 */

#include <iostream>
using std::cout;
using std::endl;
using std::ostream;

class Node{
public:
	Node(int d): data(d), left(nullptr), right(nullptr){
	}
	int data;
	Node* left;
	Node* right;
};

class Tree{
public:
	Tree(): root(nullptr){
	}
	~Tree(){
		delete_postorder(root);
	}
	void add(int d){
		if (root==nullptr)
			root = new Node(d);
		else
			add_inorder(root, d);
	}
	friend ostream& operator <<( ostream& o, Tree& t){
		o << "Inorder traversal:   ";
		t.print_inorder(o, t.root);

		o << endl << "Preorder traversal:  ";
		t.print_preorder(o, t.root);

		o << endl << "Postorder traversal: ";
		t.print_postorder(o, t.root);
		o << endl;
		return o;
	}
private:
	Node* root;

	void add_inorder(Node* t, int d){
		if (d <= t->data)
			if (t->left == nullptr)
				t->left = new Node(d);
			else add_inorder(t->left, d);
		else
			if (t->right == nullptr)
				t->right = new Node(d);
			else add_inorder(t->right, d);
	}

	void print_inorder(ostream& o, Node*t){
		if (t==nullptr) return;
		print_inorder(o, t->left);
		o << t->data << " ";
		print_inorder(o, t->right);
	}
	void print_preorder(ostream& o, Node*t){
		if (t==nullptr) return;
		print_preorder(o, t->left);
		o << t->data << " ";
		print_preorder(o, t->right);
	}
	void print_postorder(ostream& o, Node*t){
		if (t==nullptr) return;
		print_postorder(o, t->left);
		o << t->data << " ";
		print_postorder(o, t->right);
	}

	void delete_postorder(Node* t){
		if (t== nullptr) return;
		delete_postorder( t->left );
		t->left = nullptr;
		delete_postorder( t->right );
		t->right = nullptr;
		delete t;
	}
};


int main(){
	Tree t;
	int data[] = { -2, 3, 10, -21, 35, 3, 85, -2, 100};

	for (int i=0; i<9; i++)
		t.add( data[i] );

	cout << t << endl;

	cout << "Done!";
}
